//左孩子右兄弟
//typedef int DataType
//struct TreeNode
//{
//	struct TreeNode* firstChild1;
//	struct TreeNode* pNextBrother;
//	DataType data;
//};

#include"Heap.h"

void TestHeap()
{
	HP hp;
	HeapInit(&hp);
	int a[] = { 27,15,19,18,28,65,49,25,37 };
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);
	}
	HeapPrint(&hp);

	HeapPush(&hp, 10);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

}

//1.这种排序的前提是你得先有一个堆
//2.有O(N)空间复杂度
//void HeapSort(int* a, int n)//需要将一个数组的数据进行升序或降序排序
//{
//	HP hp;//创建堆
//	HeapInit(&hp);
//	for (int i = 0; i < n; i++)
//	{
//		HeapPush(&hp, a[i]);//再把数据放进堆去（边放边调整）
//	}
//
//	int i = 0;
//	while (!HeapEmpty(&hp))
//	{
//		a[i++] = HeapTop(&hp);//然后再将调整完的数据再放回数组中
//		HeapPop(&hp);
//	}
//	HeapDestory(&hp);
//}

//升序---建大堆
//降序---建小堆
void HeapSort(int* a, int n)
{
	//建堆方式1：O(N*logN)
	for (int i = 1; i < n; i++)
	{
		AjustUp(a, i);//类似于堆的插入，要从头一个个插
	}
	//建堆方式2：O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		//向下调整的前提是左右子树必须是大/小堆
		AjustDown(a, n, i);//找倒数第一个非叶子节点开始
	}

	//O(N * logN);
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AjustDown(a, end, 0);
	}
}